/*
 * Project: Set Sample
 * Copyright (C) 2013 alf.labs gmail com,
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package com.alflabs.setsample.model;

import android.util.Log;
import com.alflabs.utils.RSparseBooleanArray;
import com.alflabs.annotations.NonNull;
import com.alflabs.annotations.Null;

import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class SetSolver {

    private static final String TAG = SetSolver.class.getSimpleName();

    @NonNull
    public static Set<SetSolution> solveBoard(@NonNull final SetModel boardModel) {
        return solveBoard(boardModel.getBoard());
    }

    /**
     * Brute-force solve a board.
     *
     * @param board A non-null board to solve.
     * @return A list of solutions, possibly empty, but never null.
     */
    @NonNull
    public static Set<SetSolution> solveBoard(@NonNull final SetBoard board) {
        /*
         * A board has 12 cards.
         * 12 cards = 11*10=110 possible groups of 3 cards.
         * Try all combinations, avoiding those already tested.
         */
        final int SXY = SetBoard.SXY;
        Set<SetSolution> solutions = new TreeSet<SetSolution>();
        RSparseBooleanArray tested = new RSparseBooleanArray((SXY-1)*(SXY-2));

        for (int k1 = 0; k1 < SXY; k1++) {
            int code1 = 1<<k1;
            SetCard c1 = board.mCards[k1];

            for (int k2 = 0; k2 < SXY; k2++) {
                if (k1 == k2) continue; // can't compare same card
                int code2 = code1 | (1<<k2);
                SetCard c2 = board.mCards[k2];

                for (int k3 = 0; k3 < SXY; k3++) {
                    if (k1 == k3 || k2 == k3) continue; // can't compare same cards
                    int code3 = code2 | (1<<k3);
                    if (tested.get(code3)) continue;    // already tested
                    tested.put(code3, true);

                    SetCard c3 = board.mCards[k3];

                    if (SetCard.isSet(c1, c2, c3)) {
                        solutions.add(new SetSolution(c1, c2, c3));
                    }
                }
            }
        }

        return solutions;
    }

    /**
     * Initializes a board that contains at least 4 sets.
     *
     * @param board A non-null board to initialize. All cells will be replaced.
     * @param solutions If non-null, the known 4 sets will be added here. There might be more solutions.
     */
    @NonNull
    public static SetBoard initBoard4(
            final long modelSeed,
            @NonNull final SetBoard board,
            @Null Set<SetSolution> solutions) {
        /*
         * computing 4 solutions in a board of 12 is easy:
         * - make 4 groups of 3 cards.
         * - for each group, for each dimension: rnd select all-equal or all-different, set the dimension
         *   in the cells.
         *   => if we choose a card already used, retry.
         *   => if we choose a solution already used, retry.
         * - to make it less obvious, randomize the order of the cards.
         */

        final int SXY  = SetBoard.SXY;

        final RSparseBooleanArray cardsUsed = new RSparseBooleanArray();

        if (solutions == null) {
            solutions = new HashSet<SetSolution>();
        }

        final Random rnd = new Random(modelSeed);

        int k = 0;
        for (int limit = 10000; solutions.size() < 4 && --limit > 0; ) {
            SetCard c1 = new SetCard();
            SetCard c2 = new SetCard();
            SetCard c3 = new SetCard();

            for (int dimension = 0; dimension < SetCard.NUM_DIM; dimension++) {
                boolean eq = rnd.nextBoolean(); // equal or different
                int n = rnd.nextInt(SetCard.NUM_VALUES);
                if (eq) {
                    c1.setDimension012(dimension, n);
                    c2.setDimension012(dimension, n);
                    c3.setDimension012(dimension, n);
                } else {
                    c1.setDimension012(dimension, n);
                    n = (n+1) % SetCard.NUM_VALUES;
                    c2.setDimension012(dimension, n);
                    n = (n+1) % SetCard.NUM_VALUES;
                    c3.setDimension012(dimension, n);
                }
            }

            if (c1.equals(c2) && c2.equals(c3)) {
                // can't pick up the same 3 cards
                if (SetModel.DEBUG) Log.d(TAG,
                        String.format("[initBoard4 / x%08x / k=%d] Skip 3 same cards: %s",
                                modelSeed, k, c1));
                continue;
            }

            if (!SetCard.isSet(c1, c2, c3)) {
                // this should not happen, it should always form a set
                if (SetModel.DEBUG) {
                    throw new RuntimeException(
                            String.format("[initBoard4 / x%08x / k=%d] Skip not a set: %s / %s / %s",
                                    modelSeed, k, c1, c2, c3));
                }
                continue;
            }

            SetSolution s = new SetSolution(c1, c2, c3);
            if (solutions.contains(s)) {
                // solution already found, try to get a new one
                if (SetModel.DEBUG) Log.d(TAG,
                        String.format("[initBoard4 / x%08x / k=%d] Skip used solution: %s",
                                modelSeed, k, s));
                continue;
            }

            // otherwise keep the solution
            solutions.add(s);

            // and only add cards not already on the board
            if (!cardsUsed.get(c1.hashCode())) {
                board.mCards[k++].set(c1);
                cardsUsed.put(c1.hashCode(), true);
            }
            if (!cardsUsed.get(c2.hashCode())) {
                board.mCards[k++].set(c2);
                cardsUsed.put(c2.hashCode(), true);
            }
            if (!cardsUsed.get(c3.hashCode())) {
                board.mCards[k++].set(c3);
                cardsUsed.put(c3.hashCode(), true);
            }
        }

        // sanity check
        if (SetModel.DEBUG && solutions.size() < 4) {
            throw new RuntimeException("initBoard4: only generated " + solutions.size() + " solutions for k=" + k);
        }

        // make sure we generated enough cards
        for (int limit = 10000; k < SXY && --limit > 0; ) {
            SetCard c = board.mCards[k++];
            c.randomize(rnd);
            while (cardsUsed.get(c.hashCode()) && --limit > 0) {
                c.randomize(rnd);
            }
            cardsUsed.put(c.hashCode(), true);
        }

        // sanity check
        if (SetModel.DEBUG && k < SXY) {
            throw new RuntimeException("initBoard4: only " + k + " cards instead of " + SXY);
        }

        board.randomizeOrder(rnd);
        return board;
    }
}
